//leetcode_101:对称二叉树
//给定一个二叉树，检查它是否是镜像对称的。
//  例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
public class leetcode_101 {

    public boolean isSymmetric(TreeNode root) {

        return check(root, root);
    }
    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
//    复杂度分析：
//    时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
//    空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
